package com.exam.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: xin.wang  E-mail:xin.wang1@myt11.com
 * @CreateTime: 2022/1/17 13:52
 * @Description: 括号生成
 */
public class FourthPractice {
    /**
     * 给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
     * 例如，给出n=3，解集为：
     * "((()))", "(()())", "(())()", "()()()", "()(())"
     * <p>
     * 示例1
     * 输入：1  返回值：["()"]
     * <p>
     * 示例2
     * 输入：2  返回值：["(())","()()"]
     *
     * @param args
     */
    public static void main(String[] args) {
        FourthPractice fourthPractice = new FourthPractice();
        System.out.println(fourthPractice.generates(3));
//        getBrackets(3);
    }


    public List<String> generates(int n) {
        List<String> result = new ArrayList<>();
        combination("", n, n, result);
        return result;
    }

    /**
     * @param c        上层递归的结果
     * @param leftNum  左括号的数量
     * @param rightNum 右括号的数量
     * @param result
     */
    public void combination(String c, int leftNum, int rightNum, List<String> result) {
        //如果还未组合的左右括号数量都为0表示已经组成好了
        if (leftNum == 0 && rightNum == 0) {
            result.add(c);
            return;
        }

        if (leftNum > 0) { // 3-0  CCC
            combination(c + "(",leftNum - 1, rightNum, result);
        }

        if (rightNum > leftNum) { //3 -0 )))  right : 3
            combination(c + ")",leftNum, rightNum - 1, result);
        }

    }

  /**
   * 括号生成：
   *
   *  right:3  left:1
   *  right 2: left:1

   *  right 1 left:1
   *
   *
   *  right:3 left:2
   *  right:2 left:2
   *
   *  right:3  left:3
   *
   *
   *
   *
   *
   *  2-》3
   *  3 -》3
   *
   * ( (() ))  left : 3-2-1  right : 3-2-1
   *
   * (( )())  left 向上回溯一层： right:3   left:1
   *
   * (()  ) () right：1 left:1 right: 2-1 left：2-1
   *
   * () (()) right: 2-1 left: 2-1 right：1 left:1
   *
   * ()()() right:1 left：1
   */

  //    public static String[] getBrackets(int n){
  //        String[] brackets = new String[n*n];
  //        String bracket = new String();
  //
  //        for (int i = 0;i<n;i++){
  //            bracket += "(";
  //        }
  //        for (int i = 0;i<n;i++){
  //            bracket += ")";
  //        }
  //        brackets[0] = bracket;
  //
  //        int k = 1;
  //        for (int i = 1;i<n;i++) {
  //            for (int j = 2 * n - 2; j > n - 1; j--) {
  //                StringBuilder bracketBuild = new StringBuilder();
  //                bracketBuild.append(bracket);
  //                if (bracket.charAt(j) != bracket.charAt(i)) {
  //                    char right = bracket.charAt(j);
  //                    char left = bracket.charAt(i);
  //
  //                    bracketBuild.replace(i, i + 1, String.valueOf(right));
  //                    bracketBuild.replace(j, j + 1, String.valueOf(left));
  //
  //                    brackets[k] = String.valueOf(bracketBuild);
  //                    k++;
  //                }
  //            }
  //        }
  //        for (String bracketss:brackets) {
  //            System.out.print(Arrays.asList(bracketss));
  //        }
  //
  //        return brackets;
  //
  //    }

}
